/**
 * @author huchuc@vip.qq.com
 * @date: 2019/10/12
 */
public class HashMap<K, V> implements Map<K, V> {
    /**
     * 最大容量 1073741824
     */
    static final int     MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 负载因子
     */
    private      float   loadFactor       = 0.75f;
    /**
     * 初始容量
     */
    private      int     capacity         = 16;
    /**
     * 数组数据
     */
    private      Entry[] table;
    /**
     * 已放入数据数量
     */
    private      int     size;
    /**
     * 阈值
     */
    private      int     threshold;

    public HashMap() {
        init();
    }

    public HashMap(int initialCapacity, float initialloadFactor) {
        this.capacity = initialCapacity;
        this.loadFactor = initialloadFactor;
        init();
    }

    void init() {
        this.table = new Entry[capacity];
        //计算阈值，put元素超过该阈值将进行扩容
        this.threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public V get(K key) {
        Entry<K, V> entry = findEntry(key, indexFor(key));
        return null == entry ? null : entry.getValue();
    }

    /**
     * 扩容
     *
     * @param newCapacity
     */
    private void resize(int newCapacity) {
        capacity = newCapacity;
        //新创建一个容器
        Entry[] newTable = new Entry[newCapacity];
        for (Entry<K, V> e : table) {
            while (e != null) {
                //取得链表下一个元素
                Entry next = e.next;
                //重新计算当前元素下标位置
                int index = indexFor(e.hash);
                //已经存在的放入next，让自己成为高位链表，链表会出现倒置
                //将当前已存在的元素放入链表next
                e.next = newTable[index];
                //将当前元素放入数组
                newTable[index] = e;
                //将下一个元素赋值进行判断
                e = next;
            }
        }
        table = newTable;
        //重新计算阈值，put元素超过该阈值将进行扩容
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    /**
     * 会返回旧的value
     *
     * @param key
     * @param value
     * @return
     */
    @Override
    public V put(K key, V value) {
        //计算存储位置下标
        int index = indexFor(key);
        Entry<K, V> oldEntry = table[index];
        if (null == oldEntry) {
            //当前下标无数据，放入元素
            addEntry(index, new Entry(key, value, key.hashCode(), null));
        } else {
            //链表中查询相同key的元素
            Entry<K, V> entry = findEntry(key, index);
            if (null != entry) {
                V oldValue = entry.getValue();
                //有相同的，替换当前元素值
                entry.value = value;
                return oldValue;
            } else {
                //无相同的,放入当前元素,已存在的冲突元素放入链表
                addEntry(index, new Entry(key, value, key.hashCode(), oldEntry));
            }
        }
        return null;
    }

    private void addEntry(int index, Entry entry) {
        //数量大于等于阈值
        if (size >= threshold) {
            //扩容
            resize(2 * table.length);
            //计算新的下标位置
            index = indexFor(entry.hash);
            Entry oldEntry = table[index];
            table[index] = new Entry(entry.getKey(), entry.getValue(), entry.hash, oldEntry);
        } else {
            table[index] = entry;
        }
        size++;
    }

    /**
     * 取模运算得出分散位置
     * 计算机底层位与运算比取模运算快些
     *
     * @param key
     * @return
     */
    private int indexFor(K key) {
//        return (key == null) ? 0 : Math.abs(key.hashCode() % (capacity - 1));
        return (key == null) ? 0 : indexFor(key.hashCode());
    }

    private int indexFor(int hash) {
        return hash & (capacity - 1);
    }

    private Entry findEntry(K key, int index) {
        int hashCode = key.hashCode();
        for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
            //遍历下标下数据
            if (entry.hash == hashCode && entry.getKey().equals(key)) {
                //当前下标有数据，与已存数据的hashCode相等，key也相等
                return entry;
            }
        }
        return null;
    }

    class Entry<K, V> implements Map.Entry<K, V> {

        public final K           key;
        public       Entry<K, V> next;
        public       V           value;
        public       int         hash;

        public Entry(K key, V value, int hash, Entry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }
    }

}
